package primary.linkedList;

import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class RemoveNthFromEnd {

    /*
        双指针法
        边界条件情况，删除的是头节点.删除的是尾节点,链表中只有一个节点
        注意边界条件，边界条件调了好多次
     */
    public ListNode removeNthFromEnd(ListNode head,int n){
        ListNode fast=head,slow=head;
        // 处理删除尾节点
        if(n==1){
            // 链表只有一个元素，既是删除尾节点，又删除头节点;
            if(fast.next==null){
                return null;
            }else{
                fast=fast.next;
                while(fast.next!=null){
                    fast = fast.next;
                    slow = slow.next;
                }
                slow.next=slow.next.next;
                return head;
            }
        }

        // 删除非尾节点情况
        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }

        // 删除的是头节点
        if (fast==null){
            head= head.next;
            return head;
        }

        // 删除的不是头节点
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
            // 不用手动删除，JVM 会垃圾回收
        }

        slow.next = slow.next.next;
        return head;

    }

    /*
        官方建议标答，添加一个虚的头节点，然后所有处理变为一致，边界条件考虑较少。
     */
    public ListNode removeNthFromEnd2(ListNode head,int n){
        ListNode fakeHead = new ListNode(0,head);
        ListNode left = fakeHead,right = head;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        // 删除头节点
        if(right==null){
            return head.next;
        }

        while(right != null){
            left = left.next;
            right = right.next;
        }
        // 删除元素
        left.next = left.next.next;
        return head;
    }

}


